package chapter6;

/**
 * 大顶堆队列
 */
public class MaxPriorityQueue {

    /**
     * 插入一个值
     *
     * @param A
     * @param key
     * @return
     */
    public static int[] insert(int[] A, int key) {
        HeapSort.size = A.length + 1;
        int[] newA = new int[HeapSort.size];
        System.arraycopy(A, 0, newA, 0, A.length);
        increaseKey(newA, HeapSort.size - 1, key);
        return newA;
    }

    /**
     * 获取最大值
     *
     * @param A
     * @return
     */
    public static int max(int[] A) {
        return A[0];
    }

    /**
     * 弹出最大值
     *
     * @param A
     * @return
     */
    public static int extractMax(int[] A) {
        if (A.length == 0) {
            return -1;
        }
        int max = A[0];
        A[0] = A[HeapSort.size - 1];
        HeapSort.size = A.length - 1;
        HeapSort.maxHeap(A, 0);
        return max;
    }

    /**
     * 给第i个数赋值为key
     *
     * @param A
     * @param i
     * @param key
     */
    public static void increaseKey(int[] A, int i, int key) {
        if (key < A[i]) {
            return;
        }
        A[i] = key;
        while (i > 0 && A[HeapSort.parent(i)] < A[i]) {
            int temp = A[HeapSort.parent(i)];
            A[HeapSort.parent(i)] = A[i];
            A[i] = temp;

            i = HeapSort.parent(i);
        }
    }

}
